package main

import "sort"

/*
全排列2（有重复项数字）

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

示例1
输入：
[1,1,2]
返回值：
[[1,1,2],[1,2,1],[2,1,1]]

示例2
输入：
[0,1]
返回值：
[[0,1],[1,0]]
*/

/*
我们只要设定一个规则，保证在填第idx 个数的时候重复数字只会被填入一次即可。而在本题解中，
我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一
个未被填过的数字」，即为：
 if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
                continue
            }

假设我们有3个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其
实是保证了 [未填入，未填入，未填入][未填入，未填入，未填入] 到 [填入，未填入，未填入][填入，未填入，未填入]，
再到 [填入，填入，未填入][填入，填入，未填入]，最后到 [填入，填入，填入][填入，填入，填入] 的过程的，因此可以
达到去重的目标。

*/

func permuteUnique(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	var perm []int
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(idx int) {
		if idx == n {
			ans = append(ans, append([]int(nil), perm...))
			return
		}
		for i, v := range nums {
			if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
				continue
			}
			perm = append(perm, v)
			vis[i] = true
			backtrack(idx + 1)
			vis[i] = false
			perm = perm[:len(perm)-1]
		}
	}
	backtrack(0)
	return
}

func main() {

}
